package leetcode.weekly.week310;

//Solution4Test
public class Solution6 {

	public int lengthOfLIS(int[] nums, int k) {
		int len = 1, n = nums.length;
		if (n == 0) {
			return 0;
		}
		int[] d = new int[n + 1];
		d[len] = nums[0];
		for (int i = 1; i < n; ++i) {
			if (nums[i] > d[len] && nums[i] <= d[len] + k) {
				d[++len] = nums[i];
			} else {
				int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
				while (l <= r) {
					int mid = (l + r) >> 1;
					if (d[mid] < nums[i] && nums[i] <= d[mid] + k) {
						pos = mid;
						l = mid + 1;
					} else {
						r = mid - 1;
					}
				}
				d[pos + 1] = nums[i];
			}
		}
		return len;
	}
}
